package com.ztstudy.poi.service;


import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

class demo {
    public boolean isValid(String s) {
        //字符串为奇数
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        // 定义哈希表，存储括号匹配关系
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        // 定义栈，用于存储左括号
        Deque<Character> stack = new LinkedList<Character>();
        // 遍历字符串
        for (int i = 0; i < n; i++) {
            // 获取当前字符
            char ch = s.charAt(i);
            // 判断是否为右括号
            if (pairs.containsKey(ch)) {
                // 栈为空或栈顶元素与当前字符不匹配，则返回false
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                // 栈非空且栈顶元素与当前字符匹配，则将栈顶元素弹出
                stack.pop();
            } else {
                // 否则将当前字符入栈
                stack.push(ch);
            }
        }
        // 判断栈是否为空，若为空则说明所有括号都匹配，返回true，否则返回false
        return stack.isEmpty();
    }
    public static void main(String[] args) {
        demo d = new demo();
        System.out.println(d.isValid("[(){}][]{}"));
    }
}



